package LinkedList;

import java.util.HashMap;

public class Solution {
    class Node{

        int key;

        int val;

        Node pre,next;

        Node(){};
        Node(int key,int val){
            this.key=key;
            this.val=val;
        }


        public int getVal() {
            return this.val;
        }
    }

    class DoubleList{

        private int size;
        private Node head;
        private Node tail;

        public DoubleList(){
            head=new Node(-1,-1);
            tail=head;
            size=0;
        }

        public void add(Node node){
            tail.next=node;
            node.pre=tail;
            tail=node;
            size++;
        }

        public void delete(Node node){
            if (node==null) return;

            Node p=node.pre;
            Node n=node.next;
            p.next=n;
            node.pre=null;
            node.next=null;
            if (n==null){
                tail=head;
            }else {
                n.pre=p;
                if (n.next==null){
                    tail=n;
                }
            }
            size--;
        }

        public int getSize(){
            return this.size;
        }
    }

    private HashMap<Integer,Node> map=new HashMap();
    private DoubleList dl=null;
    private int maxSize=0;
    public Solution(int capacity) {
        // write code here
        dl=new DoubleList();
        maxSize=capacity;
    }

    public int get(int key) {
        // write code here
        if (!map.containsKey(key))
            return -1;
        Node node =map.get(key);
        int res=node.getVal();
        dl.delete(node);
        dl.add(node);
        return res;
    }

    public void set(int key, int value) {
        // write code here
        if (map.containsKey(key)){
            Node node = map.get(key);
            dl.delete(node);
            Node temp=new Node(key,value);
            map.put(key,temp);
            dl.add(temp);
        }else {
            if (dl.getSize()==maxSize){
                map.remove(dl.head.next.key);
                dl.delete(dl.head.next);
            }
            Node temp=new Node(key,value);
            map.put(key,temp);
            dl.add(temp);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution(3);
        solution.set(1,1);
        solution.set(1,2);
        System.out.println(solution.get(1));
    }
}
